package _2022.hot100._647_回文子串;

/**
 * @author： YHSimon
 * @date： 2022-06-16 16:34
 */
public class Solution {

    // 动态规划 9ms
    public int countSubstring3(String s){
        int ans=0;
        boolean[][] dp=new boolean[s.length()][s.length()];
        for(int j=0;j<s.length();j++){
            for(int i=0;i<=j;i++){
                if(s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i+1][j-1])){
                    dp[i][j]=true;
                    ans++;
                }
            }
        }
        return ans;
    }

    // 中心扩展法 6ms
    public int countSubstrings2(String s) {
        int ans = 0,n=s.length();
        for (int i = 0; i < 2 * n - 1; i++) {
            int left = i / 2;
            int right = left + i % 2;

            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }

    // 枚举 436ms
    public int countSubstrings(String s) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isValid(s.substring(i, j))) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public boolean isValid(String s) {
        for (int i = 0; i <= (s.length() - 1) / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.countSubstrings("aaa"));
    }
}
